#include "Rtree.hpp"

EntradaInterna::EntradaInterna(No *filho):Entrada(){
	int i;

	this->bb = new BoundingBox(DIM);
	this->filho = filho;

	if(filho->getEFolha()) {
        EntradaFolha **aux = (EntradaFolha**) malloc(sizeof(EntradaFolha*)*filho->getTamanho());
        for(i = 0; i < filho->getTamanho(); i++) aux[i] = static_cast<EntradaFolha*>(filho->entradas[i]);
		bb->ajustaFolha(aux, filho->getTamanho());
	}
	else{
        EntradaInterna **aux = (EntradaInterna**) malloc(sizeof(EntradaInterna*)*filho->getTamanho());
        for(i = 0; i < filho->getTamanho(); i++) aux[i] = static_cast<EntradaInterna*>(filho->entradas[i]);
		bb->ajustaInterna(aux, filho->getTamanho());
	}
}

EntradaInterna::~EntradaInterna(){
	if(this->bb) delete this->bb;
	if(this->filho) delete this->filho;
}

EntradaFolha::EntradaFolha(Ponto *p){
	if(p->getDim() == DIM)
		this->p = p;
	else this->p = NULL;
}

EntradaFolha::~EntradaFolha(){
	if(this->p) delete this->p;
}

void EntradaFolha::print(){
    this->p->print();
}

No::No(){
    this->eFolha = true;
    this->filhoFolha = false;
    this->eRaiz = true;
    this->overflow = false;
    this->tamanho = 0;
    this->altura = 1;
    this->entradas = (Entrada**) malloc(sizeof(Entrada*)*MAX);
    for(int i = 0; i < MAX; i++) this->entradas[i] = NULL;
}

No::No(bool eFolha, bool filhoFolha, bool eRaiz, int altura){
    this->eFolha = eFolha;
    this->filhoFolha = filhoFolha;
    this->eRaiz = eRaiz;
    this->overflow = false;
    this->tamanho = 0;
    this->altura = altura;
    this->entradas = (Entrada**) malloc(sizeof(Entrada*)*MAX);
    for(int i = 0; i < MAX; i++) this->entradas[i] = NULL;
}

No::~No(){
    int i;
    if(this->eFolha)
        for(i = 0; i < this->tamanho; i++){
            EntradaFolha *e = static_cast<EntradaFolha*>(this->entradas[i]);
            delete e;
        }
    else
        for(i = 0; i < this->tamanho; i++){
            EntradaInterna *e = static_cast<EntradaInterna*>(this->entradas[i]);
            delete e;
        }
}

bool No::getEFolha(){
	return this->eFolha;
}

int No::getTamanho(){
	return this->tamanho;
}

void No::decrementaTamanho(){
    this->tamanho--;
}

void No::incrementaTamanho(){
    this->tamanho++;
}

void No::print(int pai, int altura){
    int i, j;
    if(this->eFolha){
        for(i=0;i<this->tamanho;i++){
            EntradaFolha *e = static_cast<EntradaFolha*>(this->entradas[i]);
            for(j=0;j<altura;j++) printf("  ");
            e->print();
        }
    }
    else{
        for(i=0;i<this->tamanho;i++){
            for(j=0;j<(altura-this->altura);j++) printf("  ");
            printf("H: %d - Pai: %d - ", this->altura, pai);
            EntradaInterna *e = static_cast<EntradaInterna*>(this->entradas[i]);
            printf("BB(%d de %d)", i+1, this->tamanho);
            for(j=0;j<(altura-this->altura);j++) printf("  ");
            e->bb->print();
            e->filho->print(i, altura);
        }
    }
}

float No::sobreposicao(BoundingBox *bb, int pos){
	if(!this->eFolha){
        int i;
        EntradaInterna *aux;
        float sp = 0.0;

        for(i = 0; i < this->tamanho; i++)
            if(i != pos){
                aux = static_cast<EntradaInterna*>(this->entradas[i]);
                sp+= aux->bb->sobreposicao(bb);
            }

        return sp;
    }
    else return 0.0;
}

No* No::menorIncSobreposicao(Ponto *ponto, int *k, bool teste){
    if(!this->eFolha){
        if(this->tamanho == 0) return NULL;

        int i, indice;
        float   sp1, sp2, ///Sobreposição sem e com o ponto
                inc, menorInc = INFINITY; ///incremento de sobreposição e menor incremento
        EntradaInterna *aux;

        ///Para cada entrada calcular a sobreposição de sua bb com as outras entradas, sem e com o ponto
        for(i = 0; i < this->tamanho; i++){
            aux = static_cast<EntradaInterna*>(this->entradas[i]);
            sp1 = this->sobreposicao(aux->bb, i); ///sobreposição sem o ponto

            BoundingBox *comPonto = new BoundingBox(DIM); ///BB auxiliar
            aux->bb->copia(comPonto);
            comPonto->insere(ponto);
            sp2 = this->sobreposicao(comPonto, i); ///sobreposição com o ponto
            delete comPonto;

            inc = sp2 - sp1;
            if(inc < menorInc){
                menorInc = inc;
                indice = i;
            }
        }

        aux = static_cast<EntradaInterna*>(this->entradas[indice]);
        *k = indice;
        return aux->filho;
    }
    return NULL;
}

No* No::menorIncArea(Ponto *ponto, int *k){
    if(!this->eFolha){
        if(this->tamanho == 0) return NULL;

        int i, indice;
        float   area1, area2, ///Área sem e com o ponto
                inc, menorInc = INFINITY; ///Incremento de área e menor incremento
        EntradaInterna *aux;

        for(i = 0; i < this->tamanho; i++){
            aux = static_cast<EntradaInterna*>(this->entradas[i]);
            area1 = aux->bb->area();

            BoundingBox *comPonto = new BoundingBox(DIM); ///BB auxiliar
            aux->bb->copia(comPonto);
            comPonto->insere(ponto);
            area2 = comPonto->area();

            inc = area2 - area1;
            if(inc < menorInc){
                menorInc = inc;
                indice = i;
            }
        }

        aux = static_cast<EntradaInterna*>(this->entradas[indice]);
        *k = indice;
        return aux->filho;
    }
    return NULL;
}

///<Verificar se existe escolha para entradas ou nós (no lugar de ponto)>
///<Verificar se **k é necessário.>
void No::escolherSubarvore(No* raiz, Ponto *ponto, No** caminho, int *tamanho, int **k, bool teste){
	No *N = raiz;
	int t = 0, _k;

	while(1){
        if(N == NULL){
            printf("Erro na inserção.\n\n");
            *tamanho = 0;
            return;
        }
		if(N->eFolha){
            caminho[t] = N;
			(*k)[t++] = -1; ///Último nó, parar nele.
			break;
		}
		else{
            caminho[t] = N; ///Passar por N...
			if(N->filhoFolha) N = N->menorIncSobreposicao(ponto, &_k, teste);
			else N = N->menorIncArea(ponto, &_k);
            (*k)[t++]=_k; ///...e seguir para a entrada de indice _k.
		}
	}
	*tamanho = t;
}

void No::reinsercao(BoundingBox *bb, No *raiz, Ponto *p, Ponto **removidos){
    int i, j;
    float   centroBB[DIM],              ///Centro da bb do nó e d.
            distancia[this->tamanho+1]; ///Distância de todos os pontos até o centro da bb do nó
    EntradaFolha *aux;

    bb->insere(p);
    distancia[this->tamanho] = 0.0;

    for(i = 0; i < DIM; i++){
        centroBB[i] = (bb->getEixoMax(i) - bb->getEixoMin(i))/2.0;
        distancia[this->tamanho]+= SQR(p->getCoord(i) - centroBB[i]);
    }
    distancia[this->tamanho] = sqrt(distancia[this->tamanho]);

    for(i = 0; i < this->tamanho; i++){
        aux = static_cast<EntradaFolha*>(this->entradas[i]);
        distancia[i] = 0.0;
        for(j = 0; j < DIM; j++) distancia[i]+= SQR(aux->p->getCoord(j) - centroBB[j]);
        distancia[i] = sqrt(distancia[i]);
    }

    int maiores[P], t = this->tamanho;
    bool removeuPonto = false;
    kMaiores(distancia, this->tamanho + 1, P, maiores);

    for(i = 0; i < P; i++){
        maiores[i]-= t-this->tamanho;
        if(maiores[i] < this->tamanho){
            aux = static_cast<EntradaFolha*>(this->entradas[maiores[i]]);
            removidos[i] = NULL;
            aux->p->copia(&removidos[i]);
            delete aux;
            for(j = maiores[i]; j < this->tamanho-1; j++) this->entradas[j] = this->entradas[j+1];
            this->entradas[this->tamanho - 1] = NULL;
            this->decrementaTamanho();
        }
        else{
            removidos[i] = p;
            removeuPonto = true;
        }
    }

    if(!removeuPonto){
        EntradaFolha *e = new EntradaFolha(p);
        this->entradas[this->tamanho] = e;
        this->tamanho++;
    }
}

No* No::divisao(No *raiz, Ponto *p){
    int i, j,
        pos[this->tamanho+1],
        distMin[this->tamanho+1],
        minSp;

    float   margemMinima = 0.0, ///margem da bb do nó; margem da divisão de margem mínima
            coordenadas[(this->tamanho)+1]; ///valor de cada entrada em um determinado eixo

    EntradaFolha **entrada = (EntradaFolha**) malloc(sizeof(EntradaFolha*)*(this->tamanho+1)); ///Entradas que serão divididas

    for(i = 0; i < this->tamanho; i++) {
        entrada[i] = static_cast<EntradaFolha*>(this->entradas[i]);
        pos[i] = i;
    }
    pos[this->tamanho] = this->tamanho;
    entrada[this->tamanho] = new EntradaFolha(p);

    for(i = 0; i < DIM; i++){
        for(j = 0; j <= this->tamanho; j++) coordenadas[j] = entrada[j]->p->getCoord(i);
        ordenacao(coordenadas, pos, this->tamanho+1);
        ///Determina eixo em que a divisão ocorrerá --> distMin = eixo ordenado
        valorMargem(coordenadas, pos, distMin, (this->tamanho)+1, &margemMinima);
    }

    ///Determina como o eixo será dividido, i.e., quais pontos ficam em quais conjuntos
    ///minSp indica o ponto em que o segundo conjunto começa
    minSp = minSobreposicao(entrada, distMin, (this->tamanho)+1);

    ///Divide No. novo fica com segundo grupo
    No *novo = new No(true, false, false, 1);

    for(i = 0; i < minSp; i++) this->entradas[i] = entrada[distMin[i]];

    for(i = minSp; i <= this->tamanho; i++) novo->entradas[i-minSp] = entrada[distMin[i]];

    novo->tamanho = this->tamanho - minSp + 1;
    this->tamanho = minSp;

    return novo;
}

void ajustaCaminho(No **caminho, int *k, int tamanho){
    int i, j, t;

    EntradaInterna *e = static_cast<EntradaInterna*>(caminho[tamanho-2]->entradas[k[tamanho-2]]);

    t = caminho[tamanho-1]->getTamanho();
    EntradaFolha **vetor = (EntradaFolha**) malloc(sizeof(EntradaFolha*)*t);

    for(int i = 0; i < t; i++) vetor[i] = static_cast<EntradaFolha*>(caminho[tamanho-1]->entradas[i]);

    e->bb->ajustaFolha(vetor, t);

    for(i = tamanho-2; i > 0; i--){
        EntradaInterna *e = static_cast<EntradaInterna*>(caminho[i-1]->entradas[k[i-1]]);

        t = caminho[i]->getTamanho();
        EntradaInterna **vetor = (EntradaInterna**) malloc(sizeof(EntradaInterna*)*t);

        for(j = 0; j < t; j++) vetor[j] = static_cast<EntradaInterna*>(caminho[i]->entradas[j]);

        e->bb->ajustaInterna(vetor, t);
    }
}

bool No::insereEntrada(No **raiz, No **caminho, int tamanho, EntradaInterna *e){
    if((*raiz)->altura == 2) {
        No *novo = new No(false, true, false,2);
        novo->entradas[0] = e;
        novo->tamanho = 1;

        EntradaInterna  *e1 = new EntradaInterna(*raiz),
                        *e2 = new EntradaInterna(novo);

        (*raiz)->eRaiz = false;
        No *novaRaiz = new No();
        novaRaiz->entradas[0] = e1;
        novaRaiz->entradas[1] = e2;
        novaRaiz->tamanho = 2;
        novaRaiz->eFolha = false;
        novaRaiz->altura = 3;
        *raiz = novaRaiz;
        return true;
    }

    int i = tamanho - 3, altura = 3;
    No *aux = new No(false, false, false, altura);
    aux->entradas[0] = e;
    aux->incrementaTamanho();
    EntradaInterna *e_aux = new EntradaInterna(aux);

    while (caminho[i]->getTamanho() >= MAX && i>0) {
        aux = new No(false, false, false, altura++);
        aux->entradas[0] = e_aux;
        aux->incrementaTamanho();
        e_aux = new EntradaInterna(aux);
        i--;
    }

    if(caminho[i]->getTamanho() < MAX){
        //printf(" e entrou normalmente\n\n");
        caminho[i]->entradas[caminho[i]->getTamanho()] = e_aux;
        caminho[i]->incrementaTamanho();
    }
    else {
        ////printf(" e criou nova raiz\n\n");
        EntradaInterna  *e1 = new EntradaInterna(*raiz);
        (*raiz)->eRaiz = false;
        No *novaRaiz = new No();
        novaRaiz->entradas[0] = e1;
        novaRaiz->entradas[1] = e_aux;
        novaRaiz->tamanho = 2;
        novaRaiz->eFolha = false;
        novaRaiz->altura = altura;
        *raiz = novaRaiz;
        return true;
    }

    return true;
}

bool No::insere(No **raiz, Ponto *ponto, TipoReinsercao tipo, bool teste){
    No **caminho = (No**)malloc(sizeof(No*)*(*raiz)->altura); 	///Caminho da raiz até a folha encontrada
    int tamanho,												///Tamanho do caminho
        *k = (int*)malloc(sizeof(int)*(*raiz)->altura); 		///Posiçoes das entradas internas no caminho

	///Encontrar subarvore para ponto
    this->escolherSubarvore(*raiz, ponto, caminho, &tamanho, &k, teste);
    //printf("Indice %d entrou ", ponto->getIndice()); ///<tirar>

    if(caminho[tamanho-1]->tamanho < MAX){	///No folha não está cheio
        EntradaFolha *eF = new EntradaFolha(ponto);
        caminho[tamanho-1]->entradas[caminho[tamanho-1]->tamanho] = eF;
        caminho[tamanho-1]->incrementaTamanho();

		///Ajusta caminho para englobar novo ponto
        for(int i = tamanho-2; i>=0; i--){
            EntradaInterna *eI = static_cast<EntradaInterna*>(caminho[i]->entradas[k[i]]);
            eI->bb->insere(ponto);
        }
        //printf("sem problemas\n\n"); ///<tirar>
    }
    else{ /// Nó folha está cheio
        if(caminho[tamanho-1]->eRaiz){
            No *novo = caminho[tamanho-1]->divisao(*raiz, ponto);
            EntradaInterna  *e1 = new EntradaInterna(*raiz),
                            *e2 = new EntradaInterna(novo);
            (*raiz)->eRaiz = false;
            No *novaRaiz = new No();
            novaRaiz->entradas[0] = e1;
            novaRaiz->entradas[1] = e2;
            novaRaiz->tamanho = 2;
            novaRaiz->filhoFolha = true;
            novaRaiz->eFolha = false;
            novaRaiz->altura++;
            *raiz = novaRaiz;
            //printf("no split criando nova raiz\n\n"); ///<tirar>
        }
        else{
            if(caminho[tamanho-2]->overflow){
                //printf("no split");
                int pos = caminho[tamanho-2]->getTamanho();
                ajustaCaminho(caminho, k, tamanho);
                No *novo = caminho[tamanho-1]->divisao(*raiz, ponto);
                EntradaInterna *e = new EntradaInterna(novo);

                if(pos < MAX){
                    caminho[tamanho-2]->entradas[pos] = e;
                    caminho[tamanho-2]->incrementaTamanho();
                    //printf(" e entrou no nivel superior\n\n");
                }
                else {
					//printf(" e deu outro split\n\n");
					return insereEntrada(raiz, caminho, tamanho, e);
				}
            }
            else{
                //printf("com reinserção\n\n");
                EntradaInterna *e = static_cast<EntradaInterna*>(caminho[tamanho-2]->entradas[k[tamanho-2]]);
                Ponto **removidos = (Ponto**) malloc(sizeof(Ponto*)*P);

                caminho[tamanho-1]->reinsercao(e->bb, *raiz, ponto, removidos);
                caminho[tamanho-2]->overflow = true;

                ajustaCaminho(caminho, k, tamanho);

                ///Reinsere o mais distante primeiro (far reinsert)
                if(tipo == FAR_REINSERT)
                    for(int i = 0; i < P; i++) this->insere(raiz, removidos[i], tipo, false);
                ///Reinsere o mais próximo primeiro (close reinsert)
                else
                    for(int i = P-1; i >= 0; i--) this->insere(raiz, removidos[i], tipo, false);
            }
        }
    }
    return true;
}

void No::Contador(bool *k){
    int i, j;
    if(this->eFolha)
        for(i=0;i<this->tamanho;i++){
            EntradaFolha *e = static_cast<EntradaFolha*>(this->entradas[i]);
            k[e->p->getIndice()-1] = true;
        }
    else
        for(i=0;i<this->tamanho;i++){
            EntradaInterna *e = static_cast<EntradaInterna*>(this->entradas[i]);
            e->filho->Contador(k);
        }
}

void valorMargem(float coordenadas[], int pos[], int distMin[], int tamanho, float *margemMinima){
    int i;
    float d;
    bool mudou = false;

    for(i = MIN; i <= tamanho - MIN; i++){
        d = coordenadas[pos[i-1]] - coordenadas[pos[i]];
        if(d < *margemMinima){
            *margemMinima = d;
            mudou = true;
        }
    }

    if(mudou) for(i = 0; i < tamanho; i++) distMin[i] = pos[i];
}

int minSobreposicao(EntradaFolha **entradas, int distMin[], int tamanho){
    int i, j, k, pos = MIN; ///pos = indice em que o conjunto 2 começa
    BoundingBox *bb1, *bb2; ///Conjunto 1 e 2
    float sp, minSp = INFINITY; ///Sobreposição da divisão e a mínima encontrada

    bb1 = new BoundingBox(DIM);
    bb2 = new BoundingBox(DIM);

    ///Para cada possível ponto de divisão...
    ///Cada conjunto deve ter pelo menos MIN entradas.
    for(i = MIN; i <= tamanho - MIN ; i++){
        ///Primeiro conjunto
        for(k = 0; k < DIM; k++){
            bb1->setEixoMin(k,entradas[distMin[0]]->p->getCoord(k));
            bb1->setEixoMax(k,entradas[distMin[0]]->p->getCoord(k));
        }
        for(j = 1; j < i; j++){
            for(k = 0; k < DIM; k++){
                if(entradas[distMin[j]]->p->getCoord(k) < bb1->getEixoMin(k))
                    bb1->setEixoMin(k,entradas[distMin[j]]->p->getCoord(k));
                else if(entradas[distMin[j]]->p->getCoord(k) > bb1->getEixoMax(k))
                    bb1->setEixoMax(k,entradas[distMin[j]]->p->getCoord(k));
            }
        }

        ///Segundo conjunto
        for(k = 0; k < DIM; k++){
            bb2->setEixoMin(k,entradas[distMin[i]]->p->getCoord(k));
            bb2->setEixoMax(k,entradas[distMin[i]]->p->getCoord(k));
        }
        for(j = i; j < tamanho; j++){
            for(k = 0; k < DIM; k++){
                if(entradas[distMin[j]]->p->getCoord(k)< bb2->getEixoMin(k))
                    bb2->setEixoMin(k,entradas[distMin[j]]->p->getCoord(k));
                else if(entradas[distMin[j]]->p->getCoord(k) > bb2->getEixoMax(k))
                    bb2->setEixoMax(k,entradas[distMin[j]]->p->getCoord(k));
            }
        }

        ///Sobreposição dos conjuntos
        sp = bb1->sobreposicao(bb2);
        if(sp < minSp){
            minSp = sp;
            pos = i;
        }
    }

    return pos;
}

